//
// Created by Administrator on 2021/5/19.
//
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int kthLargestValue(vector<vector<int>> &matrix, int k) {
        // 求出所有位置上的XOR值
        // 二维前缀和
        // i,j位置的XOR 为其左上 上 左 matrix[i][j]的XOR和  利用异或性质  重叠为0
        // 在左 上 边包围一圈 0
        // 可以用数组+排序 或者优先队列
        auto row = matrix.size();
        auto col = matrix[0].size();
        vector<vector<int>> v(row + 1, vector<int>(col + 1, 0));
        vector<int> ans;
        for (int i = 1; i < row + 1; ++i) {
            for (int j = 1; j < col + 1; ++j) {
                v[i][j] = v[i - 1][j - 1] ^ v[i][j - 1] ^ v[i - 1][j] ^ matrix[i - 1][j - 1];
                ans.push_back(v[i][j]);
            }
        }
        sort(ans.begin(), ans.end(), greater<>());
        return ans[k - 1];
//        return pq.top();
    }

    int kthLargestValue2(vector<vector<int>> &matrix, int k) {
        auto row = matrix.size();
        auto col = matrix[0].size();
        vector<vector<int>> v(row + 1, vector<int>(col + 1, 0));
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 1; i < row + 1; ++i) {
            for (int j = 1; j < col + 1; ++j) {
                v[i][j] = v[i - 1][j - 1] ^ v[i][j - 1] ^ v[i - 1][j] ^ matrix[i - 1][j - 1];
                pq.push(v[i][j]);
                if (pq.size() > k) pq.pop();
            }
        }
        return pq.top();
    }

};

int main() {
    vector<vector<int>> mat{{5, 2},
                            {1, 6}};
    Solution sol;
    cout << sol.kthLargestValue2(mat, 1) << endl;
    cout << sol.kthLargestValue(mat, 2) << endl;
    cout << sol.kthLargestValue(mat, 3) << endl;
    cout << sol.kthLargestValue2(mat, 4) << endl;
    return 0;
}